package com.zhhe.tree;

import lombok.Data;

/*
 * Author：ZouHeng
 * Des: 大顶堆
 * Date:2021-01-17 2:02
 */
@Data
public class BigHeap {
    private int[] items;
    private int size;

    public BigHeap(int capcity) {
        items =  new int[capcity];
    }

    /**
     * 通过传入的数组直接构造大顶堆
     * @param arr
     */
    public BigHeap(int[] arr) {
        items = arr;
        this.size = arr.length;
        for (int i = (arr.length - 1) / 2; i >= 0 ; i--) {
            sink(i, arr.length - 1);
        }
    }

    public void insert(Integer value) {
        items[size] = value;
        swim(size);
        size++;
    }

    /**
     * 上浮算法
     * @param index
     */
    private void swim(int index) {
        if (index == 0) {
            return;
        }
        while (index != 0) {
            int parentIndex = (index - 1) / 2;
            Integer parentValue = items[parentIndex];
            if (parentValue < items[index]) {
                exchange(parentIndex, index);
            }
            index = index / 2;
        }
    }

    private void sink(int parentIndex, int endIndex) {
        //判断该结点是否有左孩子结点
        while (parentIndex * 2 + 1 <= endIndex) {
            //判断该结点是否有右孩子结点
            int max;
            if (parentIndex * 2 + 2 <= endIndex) {
                //比较左右孩子结点大小
                if (items[parentIndex * 2 + 1] < items[parentIndex * 2 + 2]) {
                    max = parentIndex * 2 + 2;
                } else {
                    max = parentIndex * 2 + 1;
                }
            } else {
                //该结点没有右孩子结点
                max = parentIndex * 2 + 1;
            }
            if (items[parentIndex] >= items[max]) {
                break;
            }
            exchange(parentIndex, max);
            parentIndex = max;
        }
    }

    /**
     * 下沉算法
     * @param parentIndex 插入的索引
     */
    private void sink(int parentIndex) {
        sink(parentIndex, size);
    }

    public static int[] BigHeapSort(int[] arr) {
//        BigHeap heap = new BigHeap(arr.length);
//        for (int i = 0; i < arr.length; i++) {
//            heap.insert(arr[i]);
//        }

        BigHeap heap = new BigHeap(arr);
        int index = heap.size - 1;
        while (index >= 0) {
            heap.exchange(0, index);
            index--;
            heap.sink(0,index);
        }
        return heap.getItems();
    }

    private void exchange(int preIndex, int afterIndex) {
        Integer temp = items[preIndex];
        items[preIndex] = items[afterIndex];
        items[afterIndex] = temp;
    }

    public static void main(String[] args) {
        int[] arr = {2,3,5,6,1,10,9,8,7,4};
        int[] sortArr = BigHeap.BigHeapSort(arr);
        for (Integer item :
                sortArr) {
            System.out.println(item);
        }
    }
}
